#include<iostream>
#include<fstream>
#include<sstream>
#include<bitset>
#include<cmath>
#include<sys/time.h>
#include<cstring>
using namespace std;

const int colNum = 8399;
const int R_lineNum = colNum;
const int actual_colNum = ceil(colNum * 1.0 / 32);

void Init_Zero(unsigned int** m, int line, int col)
{
    for (int i = 0; i < line; i++)
    {
        for (int j = 0; j < col; j++)
        {
            m[i][j] = 0;
        }
    }
}

//从txt中初始化被消元行矩阵
void Init_E(unsigned int** E, int* First)
{
    unsigned int StringToNum;
    ifstream infile("/home/user/Desktop/8399，6375，4535/被消元行.txt");
    if (!infile.is_open())
        cerr << " wrong file  " << endl;

    char fin[20000] = { 0 };
    int index = 0;
    while (infile.getline(fin, sizeof(fin)) ){
        std::stringstream line(fin);
        int IsFirst = 0;         //用于判断是不是首项
        while (line >> StringToNum) {     //是首项则存入First数组
            if (IsFirst == 0) {
                First[index] = StringToNum;
                IsFirst = 1;
            }
            int offset = StringToNum % 32;
            int post = StringToNum / 32;
            int temp = 1 << offset;
            E[index][actual_colNum - 1 - post] += temp;
        }
        index++;
    }
    infile.close();
}

//从txt中初始化消元子矩阵
void Init_R(unsigned int** R)
{

    unsigned int StringToNum;
    ifstream infile("/home/user/Desktop/8399，6375，4535/消元子.txt");
    if (!infile.is_open())
        cerr << " wrong file " << endl;

    char fin[20000] = { 0 };
    int index = 0;
    while (infile.getline(fin, sizeof(fin))) {
        std::stringstream line(fin);
        int IsFirst = 0;         //用于判断是不是首项
        while (line >> StringToNum) {
            if (IsFirst == 0) {
                index = StringToNum;   //对于消元子来说首项是谁就放到哪一行里面，有很多空行
                IsFirst = 1;
            }
            int offset = StringToNum % 32;   //+1的原因是txt中给的列数是从0开始计数而不是1
            int post = StringToNum / 32;
            int temp = 1 << offset;
            R[index][actual_colNum - 1 - post] += temp;
        }
    }
    infile.close();
}

//判断消元子矩阵的某一行是否为空
bool Is_R_Null(unsigned int** R, int index)
{
    for (int i = 0; i < actual_colNum; i++)
    {
        if (R[index][i] != 0)
            return false;
    }
    return true;
}

//重置E被消元行矩阵某一行的首项值
void Reset_Efirst(unsigned int** E, int index, int* First)
{
    int i = 0;
    while (E[index][i] == 0 && i < actual_colNum)
    {
        i++;
    }
    if (i == actual_colNum)
    {
        First[index] = -1;
        return;
    }
    unsigned int temp = E[index][i];
    int j = 0;
    while (temp != 0)
    {
        temp = temp >> 1;
        j++;
    }
    First[index] = actual_colNum * 32 - (i + 1) * 32 + j - 1;
}


//特殊高斯消去串行算法
void gauss(int eNum, int* First, unsigned int** R, unsigned int** E)
{
    for (int i = 0; i < eNum; i++)
    {
        while (First[i] != -1)   //当前被消元行是否已完成消元
        {
            if (Is_R_Null(R, First[i]))  //判断是否存在首项对应的消元行
            {
            //当R消元子矩阵中没有E首项对应的行时，E的那一行完成消元，同时设置在R对应的行成为消元子
                for (int i = 0; i < actual_colNum; i++)
                {
                        R[First[i]][i] = E[First[i]][i];
                }
                First[i] = -1;  //修改首项为-1表示消元结束
                break;
            }
            else   //如果E当前行首项对应的R的消元子不为空
            {
                //E被消元行减去首项对应位置的R消元子行，本质是异或操作
                for (int i = 0; i < actual_colNum; i++)
                {
                    E[First[i]][i] = E[First[i]][i] ^ R[First[i]][i];
                }
                Reset_Efirst(E, i, First);   //某行被消元后首项要进行调整
            }
        }
    }
}

int main()
{
    ifstream infile("/home/user/Desktop/8399，6375，4535/被消元行.txt");
    if (!infile.is_open())
        cerr << " wrong file  " << endl;
    char fin[20000] = { 0 };
    int eNum = 0;
    while (infile.getline(fin, sizeof(fin)))
    {
        eNum++;
    }
    infile.close();


    //存E矩阵的首项
    int* First = new int[eNum];

    //E矩阵是被消元行矩阵
    unsigned int** E = new unsigned int* [eNum];
    for (int i = 0; i < eNum; ++i)
        E[i] = new unsigned int[actual_colNum];
    Init_Zero(E, eNum, actual_colNum);
    Init_E(E, First);

    //R矩阵是消元子矩阵
    unsigned int** R = new unsigned int* [R_lineNum];
    for (int i = 0; i < R_lineNum; ++i)
        R[i] = new unsigned int[actual_colNum];
    Init_Zero(R, R_lineNum, actual_colNum);
    Init_R(R);

    struct timeval start, end;
    double timeuse;


    gettimeofday(&start, NULL);
    gauss(eNum, First, R, E);
    gettimeofday(&end, NULL);
    timeuse = ((end.tv_sec - start.tv_sec) + (double)(end.tv_usec - start.tv_usec) / 1000000.0) * 1000;
    cout << "col=" << colNum << " gauss:" << timeuse << " ";

    return 0;
}
